#include "parser.h"
#include "translator.h"
#include "cfg.h"

#define _CFG 1
#define _TAC 2
#define _C	3
#define _REP 4

#define _NOPT	0
#define _SCP 1
#define _DSE 2

void IR2C(IR& ir, ostream& o){
	Translator translator(ir.instructions);
	translator.translate();
	translator.output(o);
}

void buildCFG(IR&ir, vector<CFG *>& cfg){
	int start = 1;
	int end;
	while(start < ir.instructions.size()){
		CFG * pCFG = new CFG(ir.instructions);
		if(pCFG->build(start) == false){
			delete pCFG;
			return;
		}
		cfg.push_back(pCFG);
		start = pCFG->end + 1;
	}
}

void deleteCFG(vector<CFG *>& cfg){
	for(int i = 0 ; i < cfg.size(); i++){
		delete cfg[i];
	}
	cfg.clear();
}

void dse(IR&ir,vector<CFG *>& cfg){
	for(int i = 0; i < cfg.size(); i++){
		do{
			cfg[i]->liveness();
		}while(cfg[i]->dse());
	}
	ir.refine();
	deleteCFG(cfg);
	buildCFG(ir, cfg);
}




void printCFG(vector<CFG *>& cfg, ostream& o){
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->output(o);
	}
}

void buildSSA(IR&ir, vector<CFG *>& cfg){
	vector<Instr> oldir = ir.instructions;
	map<int, int> newreg;
	map<int, int> newlab;
	map<int, BasicBlock *> bb;

	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->findDominators();
		cfg[i]->buildDomTree();
		cfg[i]->findDomFrontier(cfg[i]->nodes.begin()->second);
		cfg[i]->liveness();
		//cfg[i]->printDomFrontier(cout);
		cfg[i]->placePhi();
		//cfg[i]->printPhi(cout);
		bb.insert(cfg[i]->nodes.begin(), cfg[i]->nodes.end());
	}

	ir.instructions.clear();
	int c = 0;
	for(int i = 0; i < oldir.size(); i++){
		if(bb.find(i) != bb.end()){
			BasicBlock * b = bb[i];
			newlab[i] = c;
			for(int j = 0 ; j < b->phis.size(); j++){//insert phi funcs
				ir.instructions.push_back(b->phis[j]);
			}
			c += b->phis.size();
		}
		ir.instructions.push_back(oldir[i]);
		newreg[i] = c;
		c++;
	}

	//update r* label*
	for(int i = 0; i < ir.instructions.size(); i++){
		Instr& instr = ir.instructions[i];
		if(instr.param1.type == REG)
			instr.param1.value = newreg[instr.param1.value];
		else if(instr.param1.type == LABEL)
			instr.param1.value = newlab[instr.param1.value];

		if(instr.param2.type == REG)
			instr.param2.value = newreg[instr.param2.value];
		else if(instr.param2.type == LABEL)
			instr.param2.value = newlab[instr.param2.value];

		if(instr.opt == MOVE && instr.param1.type == REG && instr.param1.value == 0){
			instr.param1.value = i - 1;
		}
	}

	//rebuild cfg
	deleteCFG(cfg);
	buildCFG(ir, cfg);

	//now do renaming
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->findDominators();
		cfg[i]->buildDomTree();
		cfg[i]->rename();
	}
	
}

void removePhi(IR&ir, vector<CFG*>& cfg){
	vector<Instr> oldir = ir.instructions;
	map<int, int> newreg;
	map<int, int> newlab;
	map<int, BasicBlock *> bb;

	for(int i = 0; i < cfg.size(); i++){
		bb.insert(cfg[i]->nodes.begin(), cfg[i]->nodes.end());
	}

	ir.instructions.clear();
	int c = 0;
	for(int i = 0; i < oldir.size(); i++){
		if(bb.find(i) != bb.end()){
			BasicBlock * b = bb[i];
			newlab[i] = c;
			int nphi = 0;
			for(int j = b->in; j < b->out && oldir[j].opt==PHI; j+=2){
				nphi++;
			}
			i += (2*nphi);
		}
		ir.instructions.push_back(oldir[i]);
		newreg[i] = c;
		c++;
	}

	//update r* label*
	for(int i = 0; i < ir.instructions.size(); i++){
		Instr& instr = ir.instructions[i];
		if(instr.param1.type == REG)
			instr.param1.value = newreg[instr.param1.value];
		else if(instr.param1.type == LABEL)
			instr.param1.value = newlab[instr.param1.value];
		else if(instr.param1.type == LOCAL_VAR)
			instr.param1.var_id = -1;

		if(instr.param2.type == REG)
			instr.param2.value = newreg[instr.param2.value];
		else if(instr.param2.type == LABEL)
			instr.param2.value = newlab[instr.param2.value];
		else if(instr.param2.type == LOCAL_VAR)
			instr.param2.var_id = -1;

	}
	//rebuild cfg
	deleteCFG(cfg);
	buildCFG(ir, cfg);
}


void dseReport(vector<CFG *>& cfg, ostream& o){
	for(int i = 0; i < cfg.size(); i++){
		o<<"Function: "<< cfg[i]->entry<<endl;
		o<<"Number of statements eliminated in SCR: "<< cfg[i]->dseInSCR<<endl;
		o<<"Number of statements eliminated not in SCR: "<<cfg[i]->dseOutSCR<<endl;
	}
}

void findSCR(vector<CFG *>& cfg){
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->findSCR();
	}
}

void printSCR(vector<CFG *>& cfg, ostream& o){
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->printSCR(o);
	}
}

void scp(vector<CFG *>& cfg){
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->scp();
	}
}

void scpReport(vector<CFG *>& cfg, ostream& o){
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->printSCP(o);
	}
}

//SSA Constant Propagation
void ssacp(vector<CFG *>& cfg){
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->ssacp();
	}
}

//SSA Loop Invarient Code Motion
void ssalicm(IR& ir, vector<CFG *>& cfg){
	for(int i = 0; i < cfg.size(); i++){
		vector<vector<int> >* SCR = &cfg[i]->SCR;

		if(!cfg[i]->scr_found){
			cfg[i]->findSCR();
		}
		if(SCR->size() == 0)
			continue;

		bool changed = false;
		int scrsize = SCR->size();

		for(int j = 0; j < scrsize;){
			changed = cfg[i]->ssalicm(j);
			if(changed){
				int lines_moved = cfg[i]->lines_moved;
				int num_propagated = cfg[i]->num_propagated;
				//cout << "lines_moved: " << lines_moved << endl;
				//ir.print(cout);
				deleteCFG(cfg);
				buildCFG(ir, cfg);
				cfg[i]->findSCR();
				SCR = &cfg[i]->SCR;
				//printSCR(cfg, cout);
				//printCFG(cfg, cout);
				cfg[i]->lines_moved = lines_moved;
				cfg[i]->num_propagated = num_propagated;
			}
			else
				j++;
		}

		int lines_moved = cfg[i]->lines_moved;
		int num_propagated = cfg[i]->num_propagated;
		//printSCR(cfg, cout);
		//printCFG(cfg, cout);
		deleteCFG(cfg);
		buildCFG(ir, cfg);
		cfg[i]->findSCR();
		cfg[i]->lines_moved = lines_moved;
		cfg[i]->num_propagated = num_propagated;
	}
}

void ssalicmReport(vector<CFG *>& cfg, ostream& o){
	for(int i = 0; i < cfg.size(); i++){
		cfg[i]->printssalicm(o);
	}
}

int main(int argc, char * argv[]){
	
	//ostream& o = cout;
	//ifstream ifs("C:\\Users\\rliu\\Documents\\Visual Studio 2008\\Projects\\cs380c\\examples\\prime");
	//IR ir(cin);
	//vector<CFG *> vCFG;
	//buildCFG(ir, vCFG);
	//buildSSA(ir, vCFG);
	//ir.print(o);
	//findSCR(vCFG);
	//printSCR(vCFG, o);
	//ssacp(vCFG);
	//scpReport(vCFG, o);
	//ssalicm(ir, vCFG);
	//ssalicmReport(vCFG, o);
	//ir.print(o);
	//o<<"************************"<<endl;
	//removePhi(ir, vCFG);
	//ir.print(o);
	//deleteCFG(vCFG);

	string s;
	string arg;
	int do_ssa = 0;
	int do_scp = 0;
	int do_dse = 0;
	int do_licm = 0;
	int backend = 0;
	int ssa_output = 0;

	for(int i = 1; i < argc; i++){
		s = argv[i]; 
		if(s.find("-opt=") != string::npos){
			if(s.find("ssa") != string::npos)
				do_ssa = 1;
			if(s.find("licm") != string::npos)
				do_licm = 1;
			if(s.find("scp") != string::npos)
				do_scp = 1;
			if(s.find("dse") != string::npos)
				do_dse = 1;
		}
		
		if(s.find("-backend=") != string::npos){
			arg = s.substr(9);
			if(arg.compare("c") == 0)
				backend = _C;
			else if(arg.compare("cfg") == 0)
				backend = _CFG;
			else if(arg.compare("3addr") == 0)
				backend = _TAC;
			else if(arg.compare("rep") == 0)
				backend = _REP;
			else if(arg.compare("ssa,3addr") == 0){
				backend = _TAC;
				ssa_output = 1;
			}
			else if(arg.compare("ssa,cfg") == 0){
				backend = _CFG;
				ssa_output = 1;
			}
			else if(arg.compare("ssa,rep") == 0){
				backend = _REP;
				ssa_output = 1;
			}
		}
	}


	if(backend == 0){
		cout << "usage: "<< endl;//todo
		return 0;
	}

	ostream& o = cout;


	IR ir(cin);
	vector<CFG *> vCFG;
	buildCFG(ir, vCFG);
	findSCR(vCFG);
	//ir.print(o);
	//printCFG(vCFG, o);
	//printSCR(vCFG, o);

	if(do_ssa){
		buildSSA(ir, vCFG);

		if(do_scp == 1){
			ssacp(vCFG);
		}

		if(do_dse == 1){
			cout << "Dead Code Elimination with SSA code not implemented." << endl;
			return 0;
		}

		if(do_licm == 1){
			ssalicm(ir, vCFG);
		}
	}
	else{
		if(do_licm == 1){
			cout << "Enable SSA to do loop invarient code motion." << endl;
			return 0;
		}

		if(do_scp == 1){
			scp(vCFG);
		}
	
		if(do_dse == 1){
			dse(ir,vCFG);
		}
	}

	//if( (ssa_output == 0) && (do_ssa == 1) ){
	//	removePhi(ir, vCFG); //convert from SSA back to normal;
	//}

	switch(backend){
		case _C: 
			removePhi(ir, vCFG); //convert from SSA back to normal;
			IR2C(ir, o); break;
		case _CFG: 
			if( (ssa_output == 0) && (do_ssa == 1) ){
				removePhi(ir, vCFG); //convert from SSA back to normal;
			}
			printCFG(vCFG, o);
			break;
		case _TAC:
			if( (ssa_output == 0) && (do_ssa == 1) ){
				removePhi(ir, vCFG); //convert from SSA back to normal;
			}
			ir.print(o); break;
		case _REP:
			if(do_scp == 1){
				scpReport(vCFG, o);
			}
			if(do_dse == 1){
				dseReport(vCFG, o);
			}
			if(do_licm == 1){
				ssalicmReport(vCFG, o);
			}
			break;
	}

	deleteCFG(vCFG);

	return 0;

}
